# 最低设置位
# 对任意正整数 x，都有 bits[x]=bits[x&(x-1)]+1


def countBits(n):
    bits = [0]
    for i in range(1, n + 1):
        bits.append(bits[i & (i - 1)] + 1)
    return bits


print(countBits(2))  # [0,0,1]
print(countBits(5))  # [0,1,1,2,1,2]
